package com.zwh.algorithm.leetcode.medium;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class LeetCode445 {
    /**
     * 2023-07-13 两数相加 II
     * todo 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
     * todo 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
     * @param args
     */
    public static void main(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(4,node1);
        ListNode node3 = new ListNode(2,node2);
        ListNode node4 = new ListNode(7,node3);
        ListNode node21 = new ListNode(4);
        ListNode node22 = new ListNode(6,node21);
        ListNode node23 = new ListNode(5,node22);
        ListNode node = addTwoNumbers(node4, node23);
        while (node.next != null){
            System.out.println(node.val);
            node = node.next;
        }
        System.out.println(node.val);
//        System.out.println(addTwoNumbers(node4,node23));

    }
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        String s1 = String.valueOf(l1.val);
        while (l1.next != null){
            l1 = l1.next;
            s1 += String.valueOf(l1.val);
        };
        String s2 = String.valueOf(l2.val);
        while (l2.next != null){
            l2 = l2.next;
            s2 += String.valueOf(l2.val);
        };
        int odd = 0;
        ListNode node = null;
        int len1 = s1.length();
        int len2 = s2.length();
        for (int i = 0; i < (Math.max(len1, len2)) ; i++) {
            int j1 = 0; int j2 = 0;
            if (i< len1){
                j1 = Integer.valueOf(String.valueOf(s1.charAt(len1 -1 -i)));
            }
            if (i < len2){
                j2 = Integer.valueOf(String.valueOf(s2.charAt(len2 -1 -i)));
            }
            int sum = j1 + j2 + odd;
            odd = 0;
            if (sum >= 10){
                sum = sum %10;
                odd = 1;
            }
            ListNode node1 = new ListNode(sum, node);
            node = node1;
        }
        if (odd == 1){
            ListNode node1 = new ListNode(1, node);
            node = node1;
        }
        return node;
    }

    /**栈
     *本题的主要难点在于链表中数位的顺序与我们做加法的顺序是相反的，为了逆序处理所有数位，我们可以使用栈：把所有数字压入栈中，再依次取出相加。计算过程中需要注意进位的情况。
     */
    public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        Deque<Integer> stack1 = new ArrayDeque<Integer>();
        Deque<Integer> stack2 = new ArrayDeque<Integer>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        int carry = 0;
        ListNode ans = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int a = stack1.isEmpty() ? 0 : stack1.pop();
            int b = stack2.isEmpty() ? 0 : stack2.pop();
            int cur = a + b + carry;
            carry = cur / 10;
            cur %= 10;
            ListNode curnode = new ListNode(cur);
            curnode.next = ans;
            ans = curnode;
        }
        return ans;
    }


    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
